package com.lbx.algo.skiplist;

/**
 * 跳表的实现
 */
public class SkipList {

    private static final int MAX_LEVEL = 16;
    private static final float SKIPLIST_P = 0.5f;

    private int levelCount = 1;

    private SkipListNode head = new SkipListNode();  // 带头链表

    /**
     * 查找
     * @param value
     * @return
     */
    public SkipListNode find(int value) {
        SkipListNode p = head;
        for(int i= levelCount-1;i>0;--i){
            while (p.forwards[i] != null && p.forwards[i].data < value){
                // 找到前一节点
                p = p.forwards[i];
            }
        }
        if (p.forwards[0] != null && p.forwards[0].data == value) {
            return p.forwards[0];
        } else {
            return null;
        }
    }

    public void insert(int value){

    }

    public void delete(int value){

    }

    static final class SkipListNode {
        /**
         * 存放的元素
         */
        private int data = -1;
        /**
         * 最大层级数
         */
        private int maxLevel = 0;
        /**
         * 向前的指针
         * <p>
         * 跳表是多层的，这个向前的指针，最多和层数一样。
         */
        private SkipListNode forwards[] = new SkipListNode[MAX_LEVEL];

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();
            builder.append("{ data: ");
            builder.append(data);
            builder.append("; levels: ");
            builder.append(maxLevel);
            builder.append(" }");

            return builder.toString();
        }
    }
}
